package com.datastructure.test.findlocationinarray;

import java.util.ArrayList;

public class FindLocationInArray {

    public static void main(String[] args) {

    }

    public int findLocationInArray(int[] arr,int target){
//        int start = 0;
//        int end = arr.length-1;
//        int location = binarySearch(arr,start,end,target);
//        if(location!=-1){
//            return location;
//        }
//        for (int i = 0; i < arr.length; i++) {
//            if(arr[i]>target){
//                return i;
//            }
//        }
//        return arr.length;
        return 0;
    }

    public void removeElement(int[] arr,int target){
        ArrayList<Integer> integers = binarySearch(arr, 0, arr.length - 1, target);
        for (Integer integer : integers) {
            arr[integer]=0;
        }
    }
    private ArrayList<Integer> binarySearch(int[] arr, int start, int end, int target) {
        if(start > end){
            return new ArrayList<>();
        }
        int mid = (start+end)/2;
        int midValue = arr[mid];
        if(midValue<target){
            return binarySearch(arr,mid+1,end,target);
        } else if(midValue>target){
            return binarySearch(arr,start,mid-1,target);
        } else {
            ArrayList<Integer> result = new ArrayList<>();
            int temp = mid-1;
            while (temp>=0&&arr[temp]==target){
                result.add(temp);
                temp--;
            }
            result.add(mid);
            temp=mid+1;
            while (temp<=arr.length-1&&arr[temp]==target){
                result.add(temp);
                temp++;
            }
            return result;
        }
    }
}
